// 从 {1, 2, 3 , ..., n} 中选择 k 个数，输出所有组合
// 先选择一个数字作为临时组合，
// 然后再进入递归和上一个组合进行组合，直到终止条件则为子集，收集起来
// 进入递归下一个数字组合前，要重置当前组合状态，什么意思呢？
// 例如 n = 6、k = 3 时
// [1], k = 1
// 从头递归下一轮
// [1] + [2], k = 2,不符合子集
// 从头递归下一轮,i++
// [1] + [2] + [3], k = 3,符合子集，收入,退出当前递归
// 重置,pop 并继续当前循环
// [1] + [3], k = 2,不符合子集
// 从头递归下一轮,i++
// [1] + [3] + [4], k = 3,符合子集，收入，退出当前递归
// 重置,pop 并继续当前循环
// [1] + [4], k = 2,不符合子集
// 递归....
// 第 i 层递归直到 i == k 时，退出第 i 层递归
// 重置...
// 直到循环到达数组终点时停止遍历
// 重置，pop,继续当前循环
// [2], k = 1,不符合子集
// 从头递归下一轮,i++
// ...
// 重置,pop 并继续当前循环
// [3], k = 1,不符合子集
// 递归....
// 第 i 层递归直到 i == k 时，退出第 i 层递归

var combine = function (n, k) {
  let res = [];
  let path = [];
  const dfs = (path, start) => {
    if (path.length == k) res.push(path);
    for (let i = start; i <= n; i++) {
      path.push(i);
      dfs(path.slice(), i + 1);
      path.pop();
    }
  }
  dfs(path, 1);
  return res;
}